package sun.scheduler.util.graph;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;

/**
 * Represents an {@see Iterator} that traverses over all edges of a {@see Graph}.
 * @author mfj
 */
public class EdgeIterator<N,E> implements Iterator<Edge<N, E>>
{
    private int nextNodeId = -1;
    // count of nodes that are tkane into account
    private int nodeCount;
    // mod count
    private int expectedEdgeModCound;
    
    private LinkedList<Edge<N, E>> queue = new LinkedList<Edge<N, E>>();
    private Graph<N, E> graph;

    /**
     * Instantiates a new {@see EdgeIterator}.
     * @param graph the graph over which to iterate. 
     */
    public EdgeIterator(Graph<N, E> graph)
    {
        this.graph = graph;
        this.nodeCount = graph.getNumOfNodes();
        this.expectedEdgeModCound = graph.getEdgeModCount();
        
        initNextNodeId();
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public boolean hasNext()
    {
        return !queue.isEmpty() || nextNodeId < nodeCount;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public Edge next()
    {
        if (expectedEdgeModCound != graph.getEdgeModCount())
            throw new ConcurrentModificationException();
        if (queue.isEmpty())
        {
            if (nextNodeId >= nodeCount) 
                throw new NoSuchElementException();
            
            queue.addAll(graph.getNode(nextNodeId).outEdges);
            initNextNodeId();
        }
        return queue.pollLast();
    }


    private void initNextNodeId()
    {
        while (++nextNodeId < nodeCount)
            if (!graph.getNode(nextNodeId).outEdges.isEmpty()) break;
    }

    /**
     * Not supported.
     */
    @Override
    public void remove()
    {
        throw new UnsupportedOperationException("Not supported.");
    }   
}